#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/13 14:10
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _93_restoreIpAddresses.py
from copy import deepcopy





class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []


        def restore_ip(index, restored, count):
            if count>4:return
            if count==4 and index == len(s):
                res.append(deepcopy(restored))
                return
            for segment_len in range(1, 4):
                if index + segment_len>len(s):
                    break
                segment = s[index:index+segment_len]
                if not is_valid_ip_segment(segment):
                    continue
                suffix = "" if count == 3 else "."
                restore_ip(index + segment_len, restored + segment + suffix, count + 1)

        def is_valid_ip_segment(segment):
            # 长度不能大于 3
            if len(segment) > 3: return False

            # 1. ip 段如果是以 0 开始的话，那么这个 ip 段只能是 0
            # 2. ip 段需要小于等于 255
            return len(segment) == 1 if segment[0] == '0' else int(segment) <= 255

        restore_ip(0, "", 0)
        return res